

public class FFT {

	private static Complex temp;
	
	
	
	public static Complex[] fft(Complex[] cNs, int d) {
		int N = cNs.length;
		Complex tempCN = new Complex(N,0);
		double theta = (-2 * Math.PI * d)/N;
		int r = N/2;
		
		for (int i = 1; i <= N-1; i+=0){
			Complex w = new Complex(Math.cos(i*theta),Math.sin(i * theta));
			
			for(int k = 0; k <= N-1; k+=0){
				Complex u = new Complex(1,0);
				
				for(int m = 0; m <= r-1; m++){
					temp = cNs[k+m].minus(cNs[k+m+r]);
					cNs[k+m]= cNs[k+m].plus(cNs[k+m+r]);
					cNs[k+m+r] = temp.times(u);
					u = w.times(u);
				}
				k =(int) (k+(2*r));
			}
			i = 2*i;
			r = r/2;	
		}
		for(int i = 0; i <= N-1; i++){
			r = i;
			int k = 0;
			for(int m = 1; m <= N-1; m+=0){
				k = (2 * k) + (r % 2);
				r = r/2;
				m = 2 * m;
			}
				if(k > i){
					temp = cNs[i];
					cNs[i] = cNs[k];
					cNs[k] = temp;
				}
		}
		if(d<0){
			for(int i = 0; i <= N-1; i++){
				cNs[i] = cNs[i].divides(tempCN);
			}
		}
		return cNs;
	}
}
